/* 
    添加中间区域，包括小于区域，等于区域，大于区域
*/
let dutchFlag = function (arr, num) {
    let smallPoint = -1; //指向小于区域最后一个值
    let bigPoint = arr.length; // 指向大于区域第一个值

    for (let index = 0; index < bigPoint; index++) {
        const element = arr[index];
        if (element > num) {
            arr = swap(arr, index, --bigPoint);
            index--; // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!一定注意，当前遍历到的位置大于目标时，索引保持不变，不然该数会被混入中间等于区域。
        } else if (element < num) {
            arr = swap(arr, index, ++smallPoint);
        }
    }
    return arr;
};

function swap(array, a, b) {
    let temp = array[a];
    array[a] = array[b];
    array[b] = temp;
    return array;
}

let arr = [4, 9, 4, 5, 3, 4, 5, 6, 7, 5, 4, 1, 7, 2, 0, 7, 5, 3, 1, 5, 7, 9, 5];
let division = 4;
let res = dutchFlag(arr, division);
console.log(res);
